package com.cat.dataStructure03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-star-sum-of-a-graph/
 * @create 2025/11/7 19:40
 * @since JDK17
 */

public class Solution18 {
    public int maxStarSum(int[] vals, int[][] edges, int k) {
        int n = vals.length, ans = Integer.MIN_VALUE;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList());
        for (var p : edges) {   // 加入边
            g[p[0]].add(p[1]);
            g[p[1]].add(p[0]);
        }
        for (var d : g) {   // 按升序排序
            d.sort((a, b) -> (vals[b] - vals[a]));
        }
        for (int i = 0; i < n; i++) {
            int sum = vals[i];
            for (int j = 0; j < k && j < g[i].size(); j++) {
                int x = vals[g[i].get(j)];
                if (x < 0) {
                    break;
                }
                sum += vals[g[i].get(j)];
            }
            ans = Math.max(ans, sum);
        }

        return ans;
    }
}
